package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 23:05
 * @description: 81. 搜索旋转排序数组 II <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description/">...</a>
 **/
public class SearchRotateII {

	public boolean search(int[] nums, int target) {
		int left = 0, right = nums.length - 1;

		while (left <= right) {
			int mid = (left + right) / 2;

			if (nums[mid] == target) {
				return true;
			}

			// 无法判断哪边有序，收缩边界
			if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
				left++;
				right--;
			} else if (nums[left] <= nums[mid]) { // 左半边有序
				if (nums[left] <= target && target < nums[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			} else { // 右半边有序
				if (nums[mid] < target && target <= nums[right]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		SearchRotateII sr = new SearchRotateII();
		System.out.println(sr.search(new int[]{1, 0, 1, 1, 1}, 0));
		System.out.println(sr.search(new int[]{2, 5, 6, 0, 0, 1, 2}, 0));
		System.out.println(sr.search(new int[]{2, 5, 6, 0, 0, 1, 2}, 3));
	}
}
